๋ฌธ์
๐ Logic
public void findRemovableBlock() {
int count;
// ๋ ์ด์ ์ญ์ ๊ฐ๋ฅํ ๋ธ๋ก์ด ์์ ๋๊น์ง ์งํ
do {
count = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// ๊ฐ๋ก ๋๋ ์ธ๋ก ๋ฒ์์ ์ง์ฌ๊ฐํ ๋ธ๋ก ์ฌ๋ถ ํ์ธ
if ((i <= N - 2 && j <= N - 3 && find(i, j, 2, 3)) || (i <= N - 3 && j <= N - 2 && find(i, j, 3, 2)))
count++;
}
}
removableBlocks += count;
} while(count != 0);
}
- ์ด์ค for๋ฌธ์ผ๋ก ๋ณด๋๋ฅผ ํ์ธํ๋ฉด์, 2x3 ๋ฒ์์ 3x2 ๋ฒ์๋ฅผ ํ์ธํ์ฌ ๊ฒ์ ๋ธ๋ก 2๊ฐ๋ก ์ญ์ ํ ์ ์๋ ๋ธ๋ก์ ์๋ฅผ ์นด์ดํธํ๋ค.
private boolean find(int x, int y, int h, int w) {
// ๋น ๊ณต๊ฐ์ ์นด์ดํธ, ๋น ๊ณต๊ฐ์ 2๊ฐ๊น์ง๋ง ๊ฐ๋ฅํ๋ค. ๋ธ๋ก ๋ฒ์์ ํฌ๊ธฐ๋ 6์ด๊ณ ๋ธ๋ก์ ํฌ๊ธฐ๋ 4์ด๊ธฐ ๋๋ฌธ
int emptyCount = 0;
// ๋น ๊ณต๊ฐ์ด ์๋ ๋ธ๋ก ๋ฒํธ๋ฅผ ์ ์ฅ, ๋น ๊ณต๊ฐ์ด ์๋ ๊ฒฝ์ฐ์๋ ์ด ๊ฐ๊ณผ ๋ชจ๋ ๋์ผํด์ผ ํจ
int lastNum = -1;
for (int i = x; i < x + h; i++) {
for (int j = y; j < y + w; j++) {
// ๋น ๊ณต๊ฐ์ธ ๊ฒฝ์ฐ
if (board[i][j] == 0) {
if (!canFill(i, j)) return false;
if (++emptyCount > 2) return false;
} else {
// ๋น ๊ณต๊ฐ์ด ์๋ ๋ธ๋ก ๋ฒํธ๊ฐ ์๊ณ , ํ์ฌ ์์ญ๊ณผ ๋ค๋ฅธ ๋ฒํธ๋ผ๋ฉด ๊ฐ์ ๋ธ๋ก์ด ์๋๋ฏ๋ก ์ข
๋ฃ
if (lastNum != -1 && lastNum != board[i][j]) return false;
lastNum = board[i][j];
}
}
}
removeBlock(x, y, h, w);
return true;
}
-
ํ์ฌ ์์น์ ๊ฐ๋ก, ์ธ๋ก ๋ฒ์๋ฅผ ๊ฐ์ง๊ณ ํด๋น ๋ฒ์ ๋ด์ ๋น ๊ณต๊ฐ์ ๊ฐ์์ ๋น ๊ณต๊ฐ์ด ์๋ ๋ธ๋ก์ ๋ฒํธ๋ฅผ ์ ์ฅํ๋ค.
- ๋น ๊ณต๊ฐ์ ๊ฐ์๊ฐ 3๊ฐ ์ด์์ผ ๊ฒฝ์ฐ ์ข ๋ฃํ๋ค.
- ๋น ๊ณต๊ฐ์ด ์๋ ๋ธ๋ก ๋ฒํธ์ ๊ฐ์ง ์์ ๋ธ๋ก ๋ฒํธ๊ฐ ๋์จ ๊ฒฝ์ฐ, ๋์ผํ ๋ธ๋ก์ด ์๋๋ฏ๋ก ์ข ๋ฃํ๋ค.
๐ CODE
์ฝ๋ ๋ณด๊ธฐ/์ ๊ธฐ๐ซ
import java.util.*;
class Board {
int N;
int[][] board;
// ์ง์ธ ์ ์๋ ๋ธ๋ก์ ์
int removableBlocks = 0;
public Board(int[][] board) {
this.N = board.length;
this.board = board;
}
public void findRemovableBlock() {
int count;
// ๋ ์ด์ ์ญ์ ๊ฐ๋ฅํ ๋ธ๋ก์ด ์์ ๋๊น์ง ์งํ
do {
count = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// ๊ฐ๋ก ๋๋ ์ธ๋ก ๋ฒ์์ ์ง์ฌ๊ฐํ ๋ธ๋ก ์ฌ๋ถ ํ์ธ
if ((i <= N - 2 && j <= N - 3 && find(i, j, 2, 3)) || (i <= N - 3 && j <= N - 2 && find(i, j, 3, 2)))
count++;
}
}
removableBlocks += count;
} while(count != 0);
}
private boolean find(int x, int y, int h, int w) {
// ๋น ๊ณต๊ฐ์ ์นด์ดํธ, ๋น ๊ณต๊ฐ์ 2๊ฐ๊น์ง๋ง ๊ฐ๋ฅํ๋ค. ๋ธ๋ก ๋ฒ์์ ํฌ๊ธฐ๋ 6์ด๊ณ ๋ธ๋ก์ ํฌ๊ธฐ๋ 4์ด๊ธฐ ๋๋ฌธ
int emptyCount = 0;
// ๋น ๊ณต๊ฐ์ด ์๋ ๋ธ๋ก ๋ฒํธ๋ฅผ ์ ์ฅ, ๋น ๊ณต๊ฐ์ด ์๋ ๊ฒฝ์ฐ์๋ ์ด ๊ฐ๊ณผ ๋ชจ๋ ๋์ผํด์ผ ํจ
int lastNum = -1;
for (int i = x; i < x + h; i++) {
for (int j = y; j < y + w; j++) {
// ๋น ๊ณต๊ฐ์ธ ๊ฒฝ์ฐ
if (board[i][j] == 0) {
if (!canFill(i, j)) return false;
if (++emptyCount > 2) return false;
} else {
// ๋น ๊ณต๊ฐ์ด ์๋ ๋ธ๋ก ๋ฒํธ๊ฐ ์๊ณ , ํ์ฌ ์์ญ๊ณผ ๋ค๋ฅธ ๋ฒํธ๋ผ๋ฉด ๊ฐ์ ๋ธ๋ก์ด ์๋๋ฏ๋ก ์ข
๋ฃ
if (lastNum != -1 && lastNum != board[i][j]) return false;
lastNum = board[i][j];
}
}
}
removeBlock(x, y, h, w);
return true;
}
// ํด๋น ๊ณต๊ฐ์ ์ฑ์ธ ์ ์๋์ง ํ์ธํ๋ ํจ์, ํด๋น ํ์ ์ ํ๊น์ง๊ฐ ๋น์ด์๋์ง ํ์ธ
private boolean canFill(int x, int y) {
for (int i = 0; i < x; i++)
if (board[i][y] != 0) return false;
return true;
}
// ๋ธ๋ก ์ญ์
private void removeBlock(int x, int y, int h, int w) {
for (int i = x; i < x + h; i++)
for (int j = y; j < y + w; j++)
board[i][j] = 0;
}
public int getCount() {
return removableBlocks;
}
}
class Solution {
public int solution(int[][] board) {
Board b = new Board(board);
b.findRemovableBlock();
return b.getCount();
}
}
โ๏ธ Review
- ๋ฌธ์ ์์ฒด ์ดํด๋ ์ด๋ ต์ง ์์์ง๋ง, ๊ตฌํ์ด ์ข ๋นก์ ๋ค.
- ์ญ์ ๊ฐ ๊ฐ๋ฅํ์ง ์๋์ง ํ์ธํ๋ ๋ก์ง์ด ์ค์ํ๋ค.